package StackSecond.SwordOffer;

import java.util.Stack;

public class Collision {
    /**
     * 剑指 Offer II 037. 小行星碰撞
     * 给定一个整数数组 asteroids，表示在同一行的小行星。
     * <p>
     * 对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
     * <p>
     * 找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：asteroids = [5,10,-5]
     * 输出：[5,10]
     * 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
     * 示例 2：
     * <p>
     * 输入：asteroids = [8,-8]
     * 输出：[]
     * 解释：8 和 -8 碰撞后，两者都发生爆炸。
     * 示例 3：
     * <p>
     * 输入：asteroids = [10,2,-5]
     * 输出：[10]
     * 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
     *
     * 示例 4：
     *
     * 输入：asteroids = [-2,-1,1,2]
     * 输出：[-2,-1,1,2]
     * 解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
     *
     */
    public static int[] asteroidCollision(int[] asteroids) {
        // 创建一个栈来存放行星
        Stack<Integer> stack = new Stack<>();
        // 遍历行星数组
        for (int asteroid : asteroids) {
            /* 若当前行星方向是向左的，并且栈不为空，且栈顶行星方向是向右的且体积小于当前行星
             * 则两行星会碰撞，栈顶行星会爆炸，需要弹出栈，继续判断下一个栈顶行星，直至不满条件
             * 即栈为空或栈顶行星方向和当前行星都是向左的或栈顶行星的体积大于或等于当前行星*/
            while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroid) {
                stack.pop();
            }
            /* 若当前行星是向左，且栈顶行星方向是向右并且体积等于当前行星
             *  则两行星都会爆炸，需要弹出栈顶行星*/
            if (!stack.isEmpty() && asteroid < 0 && stack.peek() == -asteroid) {
                stack.pop();
                /* 若当前行星是向右，则可以入栈，因为不知道下一个行星的方向
                 *  若当前行星是向左，且栈为空，则可以入栈
                 * 因为它前面已经没有行星了，永远也不会碰撞
                 * 若当前行星向左，栈不为空，但栈顶行星向左，则可以入栈
                 * 因为它和前面的行星方向都相同，不会发现碰撞*/
            } else if (asteroid > 0 || stack.isEmpty() || stack.peek() < 0) {
                stack.push(asteroid);
            }
        }
        int[] ans = new int[stack.size()];
        for (int i = ans.length - 1; i >= 0; i--) {
            ans[i] = stack.pop();
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] ints = asteroidCollision(new int[]{5, 10, -5});
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
}
